class Solution(object):
    def shortestDistance(self, maze, start, destination):
        """
        :type maze: List[List[int]]
        :type start: List[int]
        :type destination: List[int]
        :rtype: int
        """
        m = len(maze)
        n = len(maze[0])
        used = [[-1 for _ in range(n)] for _ in range(m)]
        used[start[0]][start[1]] = 0

        def search(point):
            x = point[0]
            y = point[1]
            if x > 0:
                index = x
                while index - 1 >= 0 and maze[index - 1][y] == 0:
                    index -= 1
                if index != x and (used[index][y] == -1 or used[x][y] + x - index < used[index][y]):
                    used[index][y] = used[x][y] + x - index
                    search([index, y])
            if x < m - 1:
                index = x
                while index + 1 < m and maze[index + 1][y] == 0:
                    index += 1
                if index != x and (used[index][y] == -1 or used[x][y] + index - x < used[index][y]):
                    used[index][y] = used[x][y] + index - x
                    search([index, y])
            if y > 0:
                index = y
                while index - 1 >= 0 and maze[x][index - 1] == 0:
                    index -= 1
                if index != y and (used[x][index] == -1 or used[x][y] + y - index < used[x][index]):
                    used[x][index] = used[x][y] + y - index
                    search([x, index])
            if y < n - 1:
                index = y
                while index + 1 < n and maze[x][index + 1] == 0:
                    index += 1
                if index != y and (used[x][index] == -1 or used[x][y] + index - y < used[x][index]):
                    used[x][index] = used[x][y] + index - y
                    search([x, index])
        search(start)
        return used[destination[0]][destination[1]]



data = Solution()
maze = [[0, 0, 1, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 1, 0], [1, 1, 0, 1, 1], [0, 0, 0, 0, 0]]
start = [4, 3]
destination = [0, 1]
print(data.shortestDistance(maze, start, destination))
maze = [[0, 0, 1, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 1, 0], [1, 1, 0, 1, 1], [0, 0, 0, 0, 0]]
start = [0, 4]
destination = [3, 2]
print(data.shortestDistance(maze, start, destination))
maze = [[0, 0, 1, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 1, 0], [1, 1, 0, 1, 1], [0, 0, 0, 0, 0]]
start = [0, 4]
destination = [4, 4]
print(data.shortestDistance(maze, start, destination))
